package elementaryAlgorithm;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * @author 郭辉
 * @className TODO
 * @description 111. 二叉树的最小深度
 * 给定一个二叉树，找出其最小深度。
 *
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 *
 * 说明：叶子节点是指没有子节点的节点。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：2
 * 示例 2：
 *
 * 输入：root = [2,null,3,null,4,null,5,null,6]
 * 输出：5
 *
 *
 * 提示：
 *
 * 树中节点数的范围在 [0, 105] 内
 * -1000 <= Node.val <= 1000
 * 通过次数536,026提交次数1,032,595
 * @date 2023/4/6 11:21
 * @company 海康威视
 * @since 1.0.0
 */
public class Leet111 {
    public int minDepth(TreeNode root) {

        return bfs(root,null);
    }

    public int bfs(TreeNode start, TreeNode target){
        if (start == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        Set<TreeNode> visited = new HashSet<>();
        queue.add(start);
        visited.add(start);
        int step = 1;
        while (!queue.isEmpty()){
            int size = queue.size();
            //将当前队列的所有节点的向外扩散
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                //判断当前是否到达
                if (cur != null && cur.left == null && cur.right == null){
                    return step;
                }
                //将当前节点的临接节点加入队列
                /*for (TreeNode node : cur.adj()){
                    if (!visited.contains(node)){
                        queue.add(node);
                        visited.add(node);
                    }
                }*/
                if (cur!=null && !visited.contains(cur.left)){
                    queue.add(cur.left);
                    visited.add(cur.left);
                }
                if (cur!=null && !visited.contains(cur.right)){
                    queue.add(cur.right);
                    visited.add(cur.right);
                }
            }
            step++;
        }
        return step;
    }

    public static void main(String[] args) {

        TreeNode node4 = new TreeNode(7);
        TreeNode node3 = new TreeNode(15,node4,null);
        TreeNode node2 = new TreeNode(20,node3,null);
        TreeNode node1 = new TreeNode(9,null,null);
        TreeNode root = new TreeNode(3,node1,node2);
        Leet111 leet111 = new Leet111();
        System.out.println(leet111.minDepth(node4));
    }
}
